package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 区间内查询数字的频率
 */

public class Code2080 {
    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 2, 2};
        RangeFreqQuery rangeFreqQuery = new Code2080().new RangeFreqQuery(nums);

        System.out.println(rangeFreqQuery.query(2, 4, 1));
        System.out.println(rangeFreqQuery.query(1, 3, 1));

    }

    class RangeFreqQuery {

        HashMap<Integer, List<Integer>> map = new HashMap<>();

        public RangeFreqQuery(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                if (!map.containsKey(arr[i])) {
                    map.put(arr[i], new ArrayList<>());
                }
                map.get(arr[i]).add(i);
            }
        }

        public int query(int left, int right, int value) {
            List<Integer> list = map.get(value);
            if (list == null || list.isEmpty()) return 0;
            int start = lowerBound(list, left);
            if (start == list.size()) return 0;
            int end = lowerBound(list, right + 1);

            return end - start;
        }

        private int lowerBound(List<Integer> nums, int target) {
            int left = -1, right = nums.size(), mid;
            while (left + 1 < right) {
                mid = left + (right - left) / 2;
                if (nums.get(mid) >= target)
                    right = mid;
                else
                    left = mid;
            }
            return right;
        }
    }
}
